package org.apache.commons.graph.algorithms.connectivity

import org.apache.commons.graph.CommonsGraph
import org.apache.commons.graph.Graph
import org.apache.commons.graph.algorithms.connectivity.internal.ConnectedComponentHandler
import org.apache.commons.graph.utils.Assertions

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * Builder for selecting the connectivity algorithm to perform.
 * @param <V> the Graph vertices type
 * @param <E> the Graph edges type
</E></V> */
fun interface ConnectivityAlgorithmsSelector<V, E> {
    /**
     * Find all connected Component for a specific graph.
     *
     * @return A collection of the disjointed sub-graphes
     */
    fun applyingMinimumSpanningTreeAlgorithm(): Collection<List<V>>
}


/**
 * TODO Fill me!!
 *
 * @param <V> the Graph vertices type
 * @param <E> the Graph edges type
</E></V> */
internal class DefaultConnectivityAlgorithmsSelector<V, E>(
    private val graph: Graph<V, E>,
    private val includedVertices: Iterable<V>
) : ConnectivityAlgorithmsSelector<V, E> {
    /**
     * {@inheritDoc}
     */
    override fun applyingMinimumSpanningTreeAlgorithm(): Collection<List<V>> {
        val untouchedVertices: MutableList<V> = ArrayList()

        for (v in includedVertices) {
            Assertions.checkState(graph.containsVertex(v), "Vertex %s does not exist in the Graph", v)
            untouchedVertices.add(v)
        }

        val connectedVertices: MutableCollection<List<V>> = mutableListOf()

        while (untouchedVertices.size > 0) {
            val source = untouchedVertices.removeAt(0)

            connectedVertices.add(
                CommonsGraph.visit(graph).from(source).applyingDepthFirstSearch(
                    ConnectedComponentHandler(untouchedVertices)
                )!!
            )
        }
        return connectedVertices
    }
}
